package leetcode.top100;

/**
 * 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
 * <p>
 * 设计一个算法计算出最大利润。在满足以下约束条件下，
 * <p>
 * 你可以尽可能地完成更多的交易（多次买卖一支股票）:
 * <p>
 * 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
 * 示例:
 * <p>
 * 输入: [1,2,3,0,2]
 * 输出: 3
 * 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
 * <p>
 * 类似问题见{@link leetcode.a_总结分布.Code04_买股票问题}
 *
 * @date 2020/5/4 22:57
 */
public class Code309_股票最佳时机3 {
    /**
     * 三个状态：
     * 卖出：特指卖出股票的那一天
     * 冷冻期：从卖出股票的第二天开始，一直到买入股票的前一天
     * 持股：手中有股票
     * <p>
     * 动态规划：
     * dp[i][j] 表示 [0, i] 区间内，到第 i 天（从 0 开始）状态为 j 时的最大收益。
     * <p>
     * 这里 j 取三个值：
     * 0 表示卖出股票的当天
     * 1 表示持股；
     * 2 表示处在冷冻期。【卖出股票的开始的第二天就算冷冻期】
     * <p>
     * 卖出股票只能有前一天持股 ，今天卖出这种状态：
     * dp[i][0] = dp[i-1][1]+prices[i]
     * <p>
     * <p>
     * 持股可以由这两个状态转换而来：
     * dp[i][1] = Math.amx(dp[i-1][1],dp[i-1][2]-price[i])
     * （1）昨天持股，今天什么都不操作，仍然持股；
     * （2）昨天处在冷冻期，今天买了一股；
     * <p>
     * 处在冷冻期要么昨天是卖出股票 ，要么昨天仍然是冷冻期，
     * dp[i][2] = Math.max(dp[i-1][0],dp[i-1][2])
     * <p>
     * 返回结果：只能在今天卖出或者是今天是冷冻期中产生
     */
    //方式1：没有优化的dp，时空都是O(n)
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 特判
        if (len < 2) {
            return 0;
        }
        int[][] dp = new int[len][3];

        // 初始化
        dp[0][0] = 0; //卖出，今天刚买出去
        dp[0][1] = -prices[0]; //持股，今天买进，成本
        dp[0][2] = 0;//冷冻期

        for (int i = 1; i < len; i++) {
            //今天卖出，只有是昨天持股，今天卖了的情况
            dp[i][0] = dp[i - 1][1] + prices[i];
            //今天持股：昨天持股，或者是昨天是冷冻期，今天买入
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] - prices[i]);
            //冷冻期：昨天是冷冻期，或者昨天刚卖出
            dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][2]);
        }
        return Math.max(dp[len - 1][0], dp[len - 1][2]);
    }

    /**
     * 由于当天状态只与前一天状态有关，类似f(n) = f(n-1) + f(n-2)
     * 空间优化1。时间O(n)，空间O(1)
     */
    public int maxProfit2(int[] prices) {
        int len = prices.length;
        // 特判
        if (len < 2) {
            return 0;
        }
        int[][] dp = new int[2][3];

        // 初始化
        dp[0][0] = 0; //卖出，今天刚买出去
        dp[0][1] = -prices[0]; //持股，今天买进，成本
        dp[0][2] = 0;//冷冻期
        int i = 1;
        for (; i < len; i++) {
            //今天卖出，只有是昨天持股，今天卖了的情况
            dp[i & 1][0] = dp[(i - 1) & 1][1] + prices[i];
            //今天持股：昨天持股，或者是昨天是冷冻期，今天买入
            dp[i & 1][1] = Math.max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][2] - prices[i]);
            //冷冻期：昨天是冷冻期，或者昨天刚卖出
            dp[i & 1][2] = Math.max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][2]);
        }
        i--;
        return Math.max(dp[i & 1][0], dp[i & 1][2]);
    }

    /**
     * 空间优化2
     */
    public int maxProfit3(int[] prices) {
        int len = prices.length;
        // 特判
        if (len < 2) {
            return 0;
        }
        System.out.println();
        int[] f = new int[3];
        // 初始化
        f[0] = 0; //卖出，今天刚买出去
        f[1] = -prices[0]; //持股，今天买进，成本
        f[2] = 0;//冷冻期
        //保存昨天的f0和f1状态
        int preF0 = f[0];
        for (int i = 1; i < len; i++) {
            //TODO 这里用到了旧的f[1],但是这次更新f[0]之前没更新过f[1],所以可以不保存f[1]
            //今天卖出，只有是昨天持股，今天卖了的情况
            f[0] = f[1] + prices[i];
            //今天持股：昨天持股，或者是昨天是冷冻期，今天买入
            //TODO 这里用到了旧的f[2],但是在这次更新f[1]之前没更新过f[2]，所以是旧的
            f[1] = Math.max(f[1], f[2] - prices[i]);
            //冷冻期：昨天是冷冻期，或者昨天刚卖出
            //TODO 这里用到了旧的f0，但是在这里f0已经被更新最新的了，所以要保存上一次f0
            f[2] = Math.max(preF0, f[2]);
            preF0 = f[0];
        }
        return Math.max(f[0], f[2]);
    }

}
